package server.simple100;


import org.junit.Test;

/***
 * 101. 对称二叉树
 */
public class LeetCode101 {


    @Test
    public void test() {
        TreeNode root = new TreeNode(1,
                new TreeNode(2, new TreeNode(3), new TreeNode(4)),
                new TreeNode(2, new TreeNode(4), new TreeNode(3))
        );
        System.out.println(isSymmetric(root));
    }

    //           1
    //       2       2
    //    3    4   4     3
    public boolean isSymmetric(TreeNode root) {
        if(root == null ){
            return false;
        }
        StringBuilder sb1 = new StringBuilder("");
        StringBuilder sb2 = new StringBuilder("");
        nextLeft(root.left, sb1);
        nextRight(root.right, sb2);
        return sb1.toString().equals(sb2.toString());
    }

    /**
     * 从左边开始遍历
     * @param node
     * @param sb
     */
    public void nextLeft(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append("-");
            return;
        } else {
            sb.append(node.val);
        }
        if (node.left != null) {
            nextLeft(node.left, sb);
        } else {
            sb.append("-");
        }
        if (node.right != null) {
            nextLeft(node.right, sb);
        } else {
            sb.append("-");
        }
    }

    /**
     * 从右边开始遍历
     * @param node
     * @param sb
     */
    public void nextRight(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append("-");
            return;
        } else {
            sb.append(node.val);
        }
        if (node.right != null) {
            nextRight(node.right, sb);
        } else {
            sb.append("-");
        }
        if (node.left != null) {
            nextRight(node.left, sb);
        } else {
            sb.append("-");
        }

    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}

//给定一个二叉树，检查它是否是镜像对称的。
//
//         
//
//        例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
//
//        1
//        / \
//        2   2
//        / \ / \
//        3  4 4  3
//         
//
//        但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
//
//        1
//        / \
//        2   2
//        \   \
//        3    3
//         
//
//        来源：力扣（LeetCode）
//        链接：https://leetcode-cn.com/problems/symmetric-tree
//        著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。